import java.util.*;

public class Test {
    public static void main(String[] args) {
//        int[] array = {12, 5, 2, 9, 10, 7};
//        System.out.println("排序前：" + Arrays.toString(array));
//        Sort.shellsort(array);
//        System.out.println("排序后：" + Arrays.toString(array));


    }

    public static ArrayList<ArrayList<Integer>> Solution(TreeNode root) {

        ArrayList<ArrayList<Integer>> arrayLists = new ArrayList<>();
        if (root == null) {
            return arrayLists;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        boolean flg = true;

        while (!queue.isEmpty()) {
            ArrayList<Integer> arrayList = new ArrayList<>();
            int size = queue.size();
            while (size != 0) {


                TreeNode p = queue.poll();
                if (p.left != null) {

                    queue.offer(p.left);
                }
                if (p.right != null) {
                    queue.offer(p.right);
                }
                arrayList.add(p.val);
                size--;
            }
            if (flg == true) {
                flg = false;
            } else {
                Collections.reverse(arrayList);
                flg = true;
            }
            arrayLists.add(arrayList);
        }
        return arrayLists;
    }
}

class TreeNode {
    public int val;
    public TreeNode left;
    public TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }
}
